﻿#pragma once
#include<iostream>
#include<stdio.h>
#include<string>
#include<assert.h>
#include<vector>
using namespace std;

// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		 // Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =//数组
			 {
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			 };
		const unsigned long* first = __stl_prime_list;//首尾指针
		const unsigned long* last = __stl_prime_list + __stl_num_primes;

		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;// 传出最接近n的素数
	
	}


	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv)//控制hash因子（占用率）小于0.7
		{
			if ((float)_n / _tables.capacity() >= 0.7)
			{
				vector<HashData<K, V>> newtable((unsigned long)__stl_next_prime(_tables.capacity() * 2) );
				_tables.swap(newtable);
				for (int i = 0; i < newtable.size(); i++)
				{
					if(newtable[i]._state== EXIST)
						assert(Insert(newtable[i]._kv));
				}
			}

			Hash hashf;
			int setp = (int)(hashf(kv.first) % _tables.capacity());//hash函数
			if (setp < 0)
				setp += (int)_tables.capacity();


			int temp = setp;
			do
			{
				if (_tables[temp]._state == EMPTY)
				{
					_tables[temp]._kv = kv;
					_tables[temp]._state = EXIST;
					_n++;
					return true;
				}
				else
				{
					temp++;
					if (temp >= _tables.capacity())
						temp -= (int)_tables.capacity();
				}
			} while (temp != setp);
			return false;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hashf;
			int setp = hashf(key) % _tables.capacity();
			if (setp < 0)
				setp += (int)_tables.capacity();

			int temp = setp;
			do
			{
				if (_tables[temp]._state == EXIST && _tables[temp]._kv.first==key)
				{
					return &(_tables[temp]);
				}
				else
				{
					temp++;
					if (temp >= _tables.capacity())
						temp -= (int)_tables.capacity();
				}
			} while (temp != setp);
			return nullptr;
		}


		bool Erase(const K& key)
		{
			HashData<K, V>* temp = Find(key);
			if (temp!=nullptr)
			{
				temp->_state = DELETE;
				return true;
			}
			else
				return false;
		}

		void Print()
		{
			for (int i = 0; i < _tables.capacity(); i++)
			{
				if (_tables[i]._state == EXIST)
				{
					cout << _tables[i]._kv.first << " : " << _tables[i]._kv.second << endl;
				}
				else if(_tables[i]._state==DELETE)
					cout << "DELETE" << endl;
				else
					cout << "EMPTY" << endl;
			}
			cout << endl;
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
	};
}


// 实现完成后，请对整形 和 字符串完成测试
